package BFS.单词搜索;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 单词搜索: https://www.nowcoder.com/practice/987f2981769048abaf6180ed63266bb2?tpId=196&tqId=39583&ru=/exam/oj
 */
public class niuke {


    /**
     * dfs 解决单词搜索. 一定要会
     */
    int[] dx = new int[]{0, 0, 1, -1};
    int[] dy = new int[]{1, -1, 0, 0};
    int m, n;
    boolean[][] vis;
    char[] word;
    public boolean exist(char[][] board, String _word) {
        m = board.length; n = board[0].length;
        word = _word.toCharArray();
        vis = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j] == word[0]) {
                    vis[i][j] = true;
                    if(dfs(board, i, j, 1)) return true;
                    vis[i][j] = false;
                }
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, int i, int j, int pos) {
        if(pos == word.length) {
            // 找到一个答案
            return true;
        }
        // 遍历上下左右四个方向
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && word[pos] == board[x][y]) {
                vis[x][y] = true; // 标记访问过
                if(dfs(board, x, y, pos + 1)) return true;
                vis[x][y] = false; // 回溯: 恢复现场
            }
        }
        // 如果上面for循环没有返回 true. 返回false 标记 i j 这个位置不合适
        return false;
    }


    // todo bfs 错误答案 (还是去学习 DFS的版本, 比较容易理解)
    // 利用bfs
//    int[] dx = new int[]{0, 0, 1, -1};
//    int[] dy = new int[]{1, -1, 0, 0};
//    boolean[][] vis = new boolean[101][101]; // 题目总共300 * 300个岛屿
//    int m , n, len;
//    char[] word;
//    public boolean exist (String[] board, String _word) {
//
//        int m = board.length, n = board[0].length();
//        word = _word.toCharArray(); len = word.length;
//        boolean ret = false;
//        // 遍历字符数组, 来一次 bfs
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if(board[i].charAt(j) == word[0]) {
//                    // 来一次 bfs
//                    ret = bfs(board, i, j, 0);
//                    if(ret) return true;
//                    return ret;
//                }
//            }
//        }
//        return ret;
//    }
//    private boolean bfs(String[] board, int i, int j, int pos) {
//        Queue<int[]> queue = new LinkedList<>();
//        queue.offer(new int[]{i, j});
//        vis[i][j] = true;
//
//        // bfs 主逻辑
//        while(!queue.isEmpty()) {
//            int sz = queue.size();
//            pos++;
//            // 下一层入队. 弹出 sz 次
//            for (int c = 0; c < sz; c++) {
//                int[] tmp = queue.poll();
//                int a = tmp[0], b = tmp[1];
//                // 上下左右四个方向
//                for (int k = 0; k < 4; k++) {
//                    int x = a + dx[k], y = b + dy[k];
//                    if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x].charAt(y) == word[pos] && pos < len) {
//                        vis[x][y] = true;
//                        // 下一层入队
//                        queue.offer(new int[]{x, y});
//                    }
//                }
//            }
//        }
//        if(pos == len) return true;
//        return false;
//    }

}
